/*
 * MemoryManager
 *
 * SJSU CS 149 Spring 2009 Project
 *
 * Copyright 2009 Timmy Yee
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

/**
 * A MemoryManager object is encapsulated in each process, which simulates
 * local page replacement policy, since when a process needs to load a
 * page, it can only evict one of its own already-loaded page.
 * <p>
 * This object keeps track of three lists: allocated, program, and loaded.
 * The allocated list represents the frames that have been allocated to the
 * process by the scheduler. The program list represents all the virtual
 * pages of the program's machine code. The loaded list represents frames
 * that have been loaded by the memory manager and will be used by the
 * process.
 *
 * @author Keven Wong
 * @author Miaoer Yu
 * @author Timmy Yee
 */
public class MemoryManager
{
    private final int processId_;
    private final int processSize_;
    private final List<Integer> allocated_;
    private final List<Integer> program_;
    private final LinkedList<Page> loaded_;
    private int requestedPage_;

    /**
     * Constructs a per-process memory manager.
     *
     * @param processId     The ID of the owning process.
     * @param processSize   The size of the owning process.
     * @param allocated     The frames allocated by the long-time scheduler.
     */
    public MemoryManager(int processId, int processSize,
                         List<Integer> allocated)
    {
        processId_ = processId;
        processSize_ = processSize;
        allocated_ = allocated;

        program_ = new ArrayList<Integer>();
        for (int i = 0; i < processSize_; i++)
            program_.add(i);
        Collections.shuffle(program_);

        loaded_ = new LinkedList<Page>();
    }

    /**
     * Gets all the frames from both lists of pages.
     *
     * @return A list of all the frames allocated to the process.
     */
    public List<Integer> getFrames()
    {
        List<Integer> frames = new LinkedList<Integer>(allocated_);

        for (Page p : loaded_)
            frames.add(p.getFrameNumber());

        return frames;
    }

    /**
     * Checks to see if the process needs to load a page.
     *
     * @return True if loading a page is needed, false otherwise.
     */
    public boolean hasPageFaultOccurred()
    {
        double resident = (double) loaded_.size() / processSize_;

        return Util.areDoublesEqual(resident, 0) ||
               (resident > 0 && resident < 0.15 && Math.random() < 0.5) ||
               (resident >= 0.15 && resident < 0.25 && Math.random() < 0.1) ||
               (resident >= 0.25 && resident < 0.5 && Math.random() < 0.05) ||
               (resident >= 0.5 && resident < 1 && Math.random() < 0.005);
    }

    /**
     * Gets the number of the requested page from the last page fault.
     *
     * @return The page number of the requested page.
     */
    public int getRequestedPage()
    {
        return requestedPage_;
    }

    /**
     * Gets the inverted page table for the process.
     *
     * @return An inverted page table as a string.
     */
    public String getPageTable()
    {
        List<String> table = new LinkedList<String>();

        for (Page p : loaded_)
            table.add(String.format("<%d, %d> -> %d", processId_,
                                    p.getPageNumber(), p.getFrameNumber()));

        return Util.join(table, ", ");
    }

    /**
     * Chooses a victim page at random.
     *
     * @return The number of the replaced frame.
     */
    private int randomReplacement()
    {
        int randomIndex = (int) (Math.random() * loaded_.size());

        Page p = loaded_.remove(randomIndex);
        Trace.log("Victim page found (frame#: %d, pid: %d, page#: %d)",
                  p.getFrameNumber(), processId_, p.getPageNumber());
        program_.add(p.getPageNumber());

        return p.getFrameNumber();
    }

    /**
     * Chooses a victim page using the clock LRU (second-chance) algorithm.
     * <p>
     * The circular buffer is simulated with a list where the head of it
     * will point to a page that will be checked. If the reference bit is
     * true, set it to false and move the page to the end. If the reference
     * bit is false, replace it.
     * <p>
     * The actual implementation of the buffer is a doubly-linked list
     * (i.e. LinkedList), so it's O(1) for adding and removing head and
     * tail nodes.
     *
     * @return The number of the replaced frame.
     */
    private int clockReplacement()
    {
        while (true) {
            Page p = loaded_.removeFirst();

            if (p.getReferenceBit()) {
                p.setReferenceBit(false);
                loaded_.addLast(p);
            } else {
                Trace.log("Victim page found " +
                          "(frame#: %d, pid: %d, page#: %d)",
                          p.getFrameNumber(), processId_, p.getPageNumber());
                program_.add(p.getPageNumber());
                return p.getFrameNumber();
            }
        }
    }

    /**
     * Gets a page from the allocated list and puts it in the loaded list,
     * replacing some other page if necessary. This simulates the page
     * fault handler loading a page from the hard drive to the memory.
     */
    public void loadPage()
    {
        int requestedFrame;

        requestedPage_ = program_.remove(0);
        Trace.log("Page fault occurred (pid: %d, page#: %d)",
                  processId_, requestedPage_);

        if (allocated_.isEmpty())
            if (Scheduler.getMemoryAlgorithm() == Algorithm.RANDOM)
                requestedFrame = randomReplacement();
            else if (Scheduler.getMemoryAlgorithm() == Algorithm.CLOCK)
                requestedFrame = clockReplacement();
            else
                throw new IllegalStateException();
        else
            requestedFrame = allocated_.remove(0);

        loaded_.addFirst(new Page(requestedPage_, requestedFrame));
    }

    /**
     * Accesses a random page by setting the reference bit of that page.
     */
    public void accessPage()
    {
        if (loaded_.isEmpty())
            return;

        int randomIndex = (int) (Math.random() * loaded_.size());
        loaded_.get(randomIndex).setReferenceBit(true);
    }
}

